#include "ustandard/ustandard.h"
struct _node {
    int v;
};

#define NUM_NODES_IN_ARRAY  8

struct _node_array {
    unsigned int using;
    struct _node nodes[NUM_NODES_IN_ARRAY];
    struct _node_array* next;
};


int array_node_add(struct _node_array** list, int v)
{
    int ret = 0;

    assert(NUM_NODES_IN_ARRAY<=sizeof(unsigned long)*8);
    struct _node_array* node_array_free = *list;
    struct _node* node_free = NULL;
    int i;
    while(NULL != node_array_free) {
        for(i=0; i<NUM_NODES_IN_ARRAY; i++) {
            if(!(node_array_free->using & (1<<i))) {
                node_free = &node_array_free->nodes[i];
                node_array_free->using |= (1<<i);
                break;
            }
        }

        if(NULL != node_free) {
            break;
        }

        node_array_free = node_array_free->next;
    }

    if(NULL == node_free) {
        node_array_free = malloc(sizeof(struct _node_array));
        //uloginf("######malloc addr %p\n", node_array_free);
        if(NULL == node_array_free) {
            //ulogdbg("malloc error%s.\n", "(task:alloc record node)");
            ret = -1;
        }
        else {
            node_free = &node_array_free->nodes[0];
            i = 0;
            node_array_free->using = (1<<i);

            node_array_free->next = *list;
            *list = node_array_free;
        }
        //ulogdbg("*list :  %p\n", *list);
    }

    if(NULL == node_free) {
        ret = -1;
    }
    else {
        node_free->v = v;
    }

    return ret;
}


int array_node_delete(struct _node_array** list, int v)
{
    int ret = 0;

    assert(NUM_NODES_IN_ARRAY<=sizeof(unsigned long)*8);
    struct _node_array* node_array = *list;
    struct _node_array* node_array_prev = NULL;
    int i;
    int finish = 0;
    while(NULL != node_array) {
        /* traverse nodes array. */
        for(i=0; i<NUM_NODES_IN_ARRAY; i++) {
            if((node_array->using & (1<<i)) && v== node_array->nodes[i].v) {
                node_array->using &= ~(1<<i);

                /* if all the nodes in array not used, delete it. */
                if(0 == node_array->using) {
                    if(NULL == node_array_prev) {
                        *list = node_array->next;
                    }
                    else {
                        node_array_prev->next = node_array->next;
                    }
                    free(node_array);
                    node_array = NULL;
                }

                finish = 1;
                break;
            }
        }

        if(finish) {
            break;
        }

        node_array_prev = node_array;
        node_array= node_array->next;
    }

    ret = finish?0:-1;
    return ret;
}


int array_node_query(struct _node_array* list, 
        void (*cb)(void* arg, struct _node* node), void* arg)
{
    int ret = 0;

    struct _node_array* node_array = list;
    int i;
    int index_array = 0;
    //printf("query result : \n");
    while(NULL != node_array) {
        //ulogdbg("node_array using = 0x%x.\n", node_array->using);
        for(i=0; i<NUM_NODES_IN_ARRAY; i++) {
            if(node_array->using & (1<<i)) {
                cb(arg, &node_array->nodes[i]);
                //assert(0 != node_array->nodes[i].v);
                //printf("\t\t[%d:%d] 0x%x \n", index_array, i, node_array->nodes[i].v);
            }
        }

        node_array = node_array->next;
        index_array ++;
    }
    //printf("\n");

    return ret;
}


struct query_info_t {
    int num;
    int64_t total;
};


#define __CHECK                                                             \
do {                                                                        \
    query_info.total = 0;                                                   \
    query_info.num = 0;                                                     \
    array_node_query(list, cb_add, &query_info);                            \
    /*printf("\t\tquery  %d total %lld\n", query_info.num, query_info.total);*/ \
    assert(query_info.num == num_alloc);                                    \
    assert(query_info.total == query_total);                                \
}while(0)


void cb_add(void* arg, struct _node* node)
{
    struct query_info_t* query_info = arg;
    query_info->num ++;
    query_info->total += node->v;
    //ulogdbg("query_info->num = %d.\n", query_info->num);
}


#define TEST_NUM    (10240)
int ks[TEST_NUM] = {0};

void test()
{
    int num_alloc = 0;
    int num_add = 0;
    int num_delete = 0;
    int64_t query_total = 0;
    struct query_info_t query_info;
    struct _node_array* list = NULL; 
    int v;
    int ret = 0;
    int idx;
    int idx_delete;
    int tmp_idx_delete;
    int i;
    int64_t t_running = 0;
    setbuf(stderr, NULL);
    while(1) {
        /* add. */
        if(num_alloc < TEST_NUM) {
            num_add = urandft(1, TEST_NUM-num_alloc);
            //printf("+ %d.\n", num_add);
            idx = 0;
            for(i=0; i<num_add; i++) {
                //printf("++++++0 num_alloc = %d\n", num_alloc);
                v = (int)malloc(urandft(1, 10240));
                assert(0 != v); 
                while(ks[idx] != 0) {
                    idx ++;
                }
                //printf("++++++0x%x\n", v);

                assert(idx<TEST_NUM);
                ks[idx] = v;
                query_total += v;
                num_alloc ++;

                ret = array_node_add(&list, v);
                assert(0 == ret);

                //printf("++++++1 num_alloc = %d\n", num_alloc);
                //__CHECK;
            }

            //num_alloc += num_add;
            //printf("\t\trecord %d total %lld\n", num_alloc, query_total);
            __CHECK;
            t_running += num_add;
        }
        
        /* delete. */
        assert(num_alloc > 0);
        num_delete = urandft(1, num_alloc);
        //printf("- %d.\n", num_delete);
        idx = 0;
        for(i=0; i<num_delete; i++) {
            //printf("------0 num_alloc = %d\n", num_alloc);

            idx_delete = urandft(0, num_alloc-1);
            tmp_idx_delete = 0;
            idx = 0;
            while(idx < TEST_NUM) {
                if(0 != ks[idx]) {
                    if(tmp_idx_delete == idx_delete) {
                        break;
                    }
                    else {
                        tmp_idx_delete ++;
                    }
                }
    
                idx ++;
            }
            assert(idx<TEST_NUM);

            free((void*)(ks[idx]));
            //printf("------0x%x\n", (unsigned int)ks[idx]);
            query_total -= ks[idx];
            num_alloc --;

            ret = array_node_delete(&list, ks[idx]);
            ks[idx] = 0;

            //printf("------1 num_alloc = %d\n", num_alloc);
            //__CHECK;
        }

        //num_alloc -= num_delete;
        //printf("\t\trecord %d total %lld\n", num_alloc, query_total);
        __CHECK;
        //printf("\n\n\n\n\n\n");
        t_running += num_delete;

        if(t_running > 1e6) {
            fprintf(stderr, ".");
            t_running -= 1e6;
        }
    }
}


int main()
{
    test();
    return 0;
}











